package leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Solution139 {

    public static void main(String[] args) {
//        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
//        ArrayList<String> wordDict = new ArrayList<>(Arrays.asList(
//                new String[]{"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"}));
//
//        System.out.println(new Solution139().wordBreak(s,wordDict));

    }
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> dict = new HashSet(wordDict);
        //动态规划
        boolean[] dp = new boolean[s.length()+1];
        dp[s.length()] = true;
        //依次计算dp[s.length-1],dp[s.length-2]...dp[0]
        for (int i = s.length()-1; i >=0 ; i--) {
            //遍历每种可划分方式
            for (int j = s.length(); j >=i ; j--) {
                if(dp[j]&&dict.contains(s.substring(i,j))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
    public boolean wordBreak1(String s, List<String> wordDict) {
        //将s从头开始每次增加一个字符，直到找到一个在字典中的单词，s减去此单词后递归下去
        //继续添加字符，找到下一个单词，递归；如果没有符合的，返回false;
        //当递归进入时字符串空了，返回true
        //为了加快查找速度，将单词存储一个hash表
        HashSet<String> dict = new HashSet(wordDict);
        int[] cache = new int[s.length()+1]; //存储已经遍历到的s[i...end]子字符串是否可break,未变历到0,不能break为-1,能break为1
        return dfs(s,0,dict,cache);
    }

    public boolean dfs(String s, int start, HashSet<String> dict, int[] cache){
        if(start>=s.length()) return true; //s已经减掉完了
        boolean res = false;
        int i = start;
        while (i<=s.length()){ //减去每个可能的单词
            //寻找每个可减去的单词
            while (i<=s.length()&&!dict.contains(s.substring(start,i))) i++;
            //i>s.length()或者dict.contains(s.substring(start,i))
            if(i<=s.length()){
                if(cache[i]==0)
                    cache[i] = dfs(s,i,dict,cache)==true?1:-1;
                res = res || cache[i]==1;
            }
            i++;
        }
        return res;
    }

}
